The stability of strange pentaquarks $uudd\bar s$ is studied in a constituent quark model based on a flavor-spin hyperfine interaction between quarks. With this interaction model, which schematically represents the Goldstone boson exchange interaction between constituent quarks, the lowest lying strange pentaquark is a $p-$shell state with positive parity. The flavor-spin interaction lowers the energy of the lowest $p-$shell state below that of the lowest $s-$shell state, which has negative parity because of the negative parity of the strange antiquark. It is found that the strange pentaquark is stable against strong decay provided that the strange antiquark interacts by a fairly strong spin-spin interaction with $u$ and $d$ quarks. This interaction has a form that corresponds to $\eta$ meson exchange. Its strength may be inferred from the $\pi^0$ decay width of $D_s^*$ mesons.